import java.util.HashMap;
/**
 * 最长回文子串
 * 思路：
 *      使用一个HashMap记录每个字符的index，如果该字符已经存在，则更新下标
 *      维护一个left来记录回文子串的开始位置
 *      维护一个max来记录回文子串的最长长度
 */

public class LongestSubstring {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) return 0;
        if (s.length() == 1) return 1;

        HashMap<Character, Integer> map = new HashMap<>();
        int left = 0;
        int max = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (map.containsKey(s.charAt(i))) {
                // 如 abba，那么相当于把left指针置在第一个a后一位了，这样显然是扩大了域
                // 事实上，如果当前left比map.get(s.charAt(i)) + 1更大，那么我们是不需要改变left的位置的。
                // left = map.get(s.charAt(i)) + 1;
                left = Math.max(left, map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i), i);
            // 当前窗口大小 i- left + 1，与历史max取最大值
            max = Math.max(max, i - left + 1);
        }
        return max;
    }
}